/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/remove-duplicate-letters
   @Language: C++
   @Datetime: 19-04-27 15:26
   */

class Solution {
public:
	/**
	 * @param s: a string
	 * @return: return a string
	 */
	string removeDuplicateLetters(string &s) {
		// write your code here
		unordered_map<char,int> dict;
		for(const char &ch:s)
			dict[ch]++;
		unordered_set<char> vist;
		stack<char> mins;
		for(const char &ch:s){
			if(vist.count(ch)) {
				dict[ch]--;
				continue;
			}
			for(; mins.size() && mins.top()>ch && dict[mins.top()];){
				vist.erase(mins.top());
				mins.pop();
			}
			mins.push(ch);
			vist.insert(ch);
			dict[ch]--;
		}
		string str;
		for(; mins.size(); str.push_back(mins.top()), mins.pop());
		reverse(str.begin(),str.end());
		return str;
	}
};
